package leetcode_day._2021._202106._2130;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/22 10:29
 * 字符串的排列
 * 算法：回溯
 * 使用 boolean used[] 记录当前字符有没有被使用
 */
public class _22_剑指offer38 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new _22_剑指offer38().permutation("suvyls")));
    }

    public String[] permutation(String s) {
        char[] array = s.toCharArray();
        Arrays.sort(array);
        boolean[] used = new boolean[array.length];
        List<String> ans = new ArrayList<>();
        dfs(array, used, ans, new StringBuilder());
        return ans.toArray(new String[0]);
    }
    void dfs(char[] array, boolean[] used, List<String> ans, StringBuilder cur) {
        if (cur.length() == array.length) {
            ans.add(new String(cur));
            return;
        }
        for (int i = 0; i < array.length; i++) {
            if (used[i]) continue;
            if (i != 0 && array[i] == array[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            cur.append(array[i]);
            dfs(array, used, ans, cur);
            cur.delete(cur.length() - 1, cur.length());
            used[i] = false;
        }
    }

}
